'''
https://leetcode.cn/problems/the-maze/description/
'''
from collections import deque
from typing import List


class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        destination = tuple(destination)
        m, n = len(maze), len(maze[0])
        q = deque([(start[0], start[1])])
        visited = [[False] * n for _ in range(m)]
        while q:
            i, j = q.popleft()
            if (i, j) == destination: return True
            if visited[i][j]: continue
            visited[i][j] = True
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                x, y = i + dx, j + dy
                while 0 <= x < m and 0 <= y < n and maze[x][y] == 0:
                    x, y = x + dx, y + dy
                x, y = x - dx, y - dy
                q.append((x, y))
        return False
